CMU 11642 的课程笔记。这篇讲了搜索引擎中创建索引的主要原则、方法以及优化方案。

Overview

Inverted list:
索引包含了各种数据结构，如 term dictionary，inverted list 等。inverted list 是一个重点。搜索引擎所拥有的文档中出现的每一个单词都拥有一个 inverted list，记录这个单词在多少文档中出现，分别是哪些文档，每个文档分部出现多少次，分别出现在什么位置等信息。比如 Apple 这个词出现在文档 1，7，19，34，102。其中文档 1 中出现了3次，分别在位置 20，105，700。这样当搜索 Apple 时，搜索引擎就不用遍历所有的文档，只需要查找每个单词对应的 inverted list 就可以知道这个词在哪里出现了。

文档预处理:
创建索引是个巨大工程。首先是对文档进行解析和处理。互联网上的文档格式各种各样，对每一种格式的文档都要有一个对应的解析器程序，这样才能忽略各种奇怪符号，提取出有用内容。每一个解析器的实现都是一个繁琐且困难的任务。对于解析后的干净文档，许多重要的自然语言处理算法就要派上用场。以英语为例，需要进行分词（tokenization，将一句话分割成一个个单词），词干提取（stemming，将文本中出现的单词还原成它的原型），part-of-speech tagging（识别单词在一句话中的词性），创建 n-gram 模型等操作。此外还需要识别文档中的命名实体(named entity)，比如将“iphone 6”作为一个词，而不是 “iphone” 一个， “6” 一个。上述操作生成的信息都要存储下来。这样构造 inverted list 时就可以知道每个单词出现的位置，出现个数等信息。

生成索引:
索引生成程序的一个设计目标就是高效。它要求被尽可能地运行在多个机器上。对于每个机器来说，索引程序一边扫描输入文档，一边在内存中更新索引的数据结构。当内存中得数据大小超过一定阀值时，这些内容被作为一个块(block)一次性写入硬盘文件中。当所有文档扫描结束后这些块会再被合并成一个大的 inverted file。因为每一个块都是排好序的，合并操作是线性的复杂度。因为数据量太大，可以用 MapReduce 把一个大的任务分割成许多小任务，并下发给多个 Mapper 程序，Mapper计算好的中间结果会发给多个 Reducer 程序继续处理，得到最终结果。这个计算模型允许成千上万台机器同时运算，从而极大提高了运算效率。

inverted list 要和访问机制(access mechanism)一起可以工作。访问机制定义了如何通过一个单词找到它所对应的 inverted list。大概可以使用两种数据结构：b-tree 或 Hash table。

Big facts:

索引中的单词和文档都用 integer 的 ID 表示而不是字符串，省空间省时间。
一般来说 corpus 比 RAM 要大，不能在内存中完成整个任务，所以一定会有部分写到磁盘中，访问磁盘数据比访问内存数据慢得多，所以可以做的是
- 只在必要的时候写入磁盘
- 压缩数据减少 I/O。数据从磁盘传输到内存是由系统总线而不是处理器来实现的，所以磁盘 I/O 时处理器仍然可以处理数据。
- 顺序读取（比 random access 快）。因为磁盘读写时，磁头移到数据所在的磁道有一段时间，大概 5ms，称为寻道时间，这段时间并不进行数据的传输，所以连续读取的数据应该连续存放来节省时间。

索引更新:
互联网内容是不停变化的，这必然导致索引不停被更新。然而建立好的索引中，各个单词的反转列表是紧密的拼接在一起的，这使得更新变得非常困难。通常搜索引擎会积攒一批文件后才进行索引的更改，并且把索引分成静态和动态两个部分。程序把所有更改都写入动态部分，并且周期性地将动态部分合并进静态部分中。搜索时，动态和静态部分都会被访问。当从索引中删除一个文档时，这个文档中出现的词对应的反转列表都会被修改，开销极大。于是程序加入了“删除列表（delete lists）”来记录所有被删除的文档。搜索时会查询删除列表来把已经被删除的文档从搜索结果中移除。当删除列表足够大，垃圾回收机制会被触发，重新生成索引。

Single Processor(单机版)

Block sort-based indexing(BSBI)

基于块的排序索引方法(Block sort-based indexing algorithm) 过程如下:

将 corpus 分割成几个大小相等的部分
对每个部分的 (termId,docId)排序
一旦 in-memory buffer 满了，就把临时排序结果 flush 到磁盘中，然后重新初始化，重复2、3过程
将所有的中间文件合并成最终索引。(merge index blocks on disk)

BSBI 的时间复杂度是 O(TlogT)

Single-pass in-memory indexing(SPIMI)

BSBI 需要将 term 映射成 id，对大规模的 corpus 来说，这种数据结构会很大以致在内存中难以存放，SPIMI 使用 term 本身，将每个块的词典写入磁盘，对于下一个块则重新采用新的词典，这样带来的好处是，只要硬盘空间足够大，SPIMI 就能索引任何大小的 corpus。算法如下，反复调用 SPIMI-INVERT 函数直到将全部 corpus 处理完。token_stream 就是 term-docid stream。

BSBI 和 SPIMI 的一个区别是， SPIMI 直接在 inverted list 中增加一项，这个 inverted list 是动态增长对，大小会不断调整，而 BSBI 一开始就整理出所有的 termID-docID 并对它们进行排序。这样做的好处是：

不需要进行排序，处理速度更快
保留 inverted list 对 term 的归属关系，能节省内存，也不用保存 term id，所以每次单独的 SPIMI-INVERT 调用能够处理的块可以非常大，整个的索引构建过程也会因此非常高效。

SPIMI 的空间复杂度是 O(T)。

Distributed indexes

Size of web search engine index

一些假设：

网页数：500亿（2013年），假设 50％是 text 文本
平均网页大小：37K（2013年）
假设 non-text 网页的平均入链数：1K
索引大小约为原始文本大小的 20％

Text: 25billion 37K + 25billion 1K = 925TB
Index: 20% * 950TB = 185TB (call it 200TB for convenience)

–> 索引分布在 50 个 4TB 的磁盘驱动器上比较合理

Hardware

一个 computer cluster，又叫做 rack，有 40-80 台机器，每个 rack 有自己内部的网络，对大公司像 google 而言，机器的选择遵循的原则是：

越便宜越好
每台计算机使用少量的普通磁盘
每台计算机使用比较大(not huge)的 RAM

因为一台机子坏了得立刻换一台机子上去，自动部署，随时投入使用。而对于小的组织像 cmu，机子就会买好一点的，一台坏了会去修，而不是直接换一台。

Partitioned indexes

分布式索引用到了 sharding 和 replication 的原理。

Sharding

index 通常是被切片(sharding)的，每个分区包含了一堆不重复的文档集合，每个分区都被分到了一台机器，根据之前对索引大小的估计，就有 25 个分区(2 disks/node, 4TB/disk => 200TB) 。那么 corpus 会怎样被分区呢？ 可以随机分配(random assignment)，也可以按来源（source-based assignment），总的来说，随机分配用的比较多，因为随机可以平衡不同分区的 query traffic，让每台机得到充分使用。

Replication

索引通常被存了好几份 copy(replication)，为了提高并行能力和容错能力。所以一个 index server 标准的配置：

40 machines in a rack
2*4TB disks/machine
320 TB of index/rack

Query evalution

分布式系统的 query 评估过程为

从每个分区中找出一台机器。 (select a machine for each index partition)
把 query 分配到选出的机器中，然后每台机器返回一个 ranked list of matches。 (broadcast the query to each selected machine)
一个 aggregator 将这些 ranked list 合并(merge-sort)成最终的有序文档集合。(an aggregator assembles them into a final ranked list of doc ids)
其它机器对每个结果来寻找 title, urls, etc.。（other machines looks up titles, URLs, etc., for each result, a similar partitioning/pooling strategy is used for documents）

Tiered indexes

另一种分布式的 index 是将 web page 进行分层，10% 为 tier 1，是高价值的网页，其余 90% 是 tier 2，是低价值的网页。query 过来我们先从 tier 1 找，如果 good results 不够，再往 tier 2 找。所以问题来了，怎么找 top tier(s)？

page rank 较高的网页，或来自 page rank 较高的网站的网页
对之前的一些常见 query 非常重要的网页（排名高，点击率高，停留时间长）
网址较短的网页（更可能是主页）
spam 分数较低的网页

Tiered index 的优势如下：

降低了大多数 query 的搜索成本，一个完整的搜索过程比 tier 1 的搜索要找 10x 的机器。
提高了大多数 query 的搜索质量，因为它更关注 “good” pages.

什么情况下会去找 tier 2?

匹配 query 的 Tier 1 的网页太少
query 非常少见

Index Construction

建立分布式索引用的框架是 MapReduce，基本过程是 Input reader –> Map –> Combine –> Shuffle –> Reduce。
从最基本的 binary inverted list 进行示范，format 是 (term,[docids]) 或者 (term,[docid,docid,…])，注意这里的 docid 是 internal document id（转化成了 integer）而不是原来的 id。

Mapper

每个 Map task 相当于一个 document parser

input: a stream of documents
output: a stream of (term,docid) tuples
eg. (men,1)(and,1)(women,1)…(once,2)(upon,2)

Shuffle／Sort

Shuffle 的过程相当于 route tuples 到 Reducers 里。在 Shuffle/Sort 中，都是 shuffle/sort by key，而不是 by value。

input: (t5,docid1)(t1,docid3)(t1,docid1)…
output: (t1,docid3)(t1,docid1)(t5,docid1)…

Redcuer

Reducer 的作用就是将 stream of keys 转化成 streams of inverted lists。Reducer 会 sort values 也就是 docids，然后建立 inverted list，这里要保证的是最长的 inverted list 必须能够 fit in memory。

input: (men,1)(men,127)(men,49)(men,23)…
ouput: (men,[df:492,docids:1,23,49,127,…])

Improvement

这个流程下来的效率并不高，因为文档里所有 unique term 都会产生一个 tuple，像 WSJ’87-92 (533 MB of text) 就会产生 20 million 的 tuple，每个 tuple 都会 shuffle 到 reducers 里，进 reducer 前还要先 sort，这个过程特别耗时。所以我们会用 Combiner 来提高效率。Combiner 的作用和 reducer 差不多，不过它是在每个 mapper 里进行的，它把每个 mapper 里的 docid 先进行了合并。(t1,docid1)(t2,docid1)(t4,docid2)…->(t1,[docid1,docid18,…])。这样的好处是需要 shuffle 的 tuple 更少，需要 hash 的 key 更少，需要进行 movement operation 的数据也更少，另外，需要 reduce 的 tuple 更少，需要 sort 的 tuple 也更少。
改进后的框架如下：

Map:
$(docid_1,content_1)$ -> $(t_1,ilist_{1,1})(t_2,ilist_{2,1})(t_3,ilist_{3,1})$
Combine:
Sort by t & combine $(t_1 [ilist_{1,2} ilist_{1,3} ilist_{1,1},…])$->$(t_1,ilist_{1,27})$
每个 output inverted list 包含了一系列文档
Shuffle by t
Sort by t
$(t_4 ilist_{4,1}) (t_1 ilist_{1,3})$->$(t_1,ilist_{1,2})(t_1,ilist_{1,4})(t_4,ilist_{4,1})$
Reduce
$(t_1 [ilist_{1,2} ilist_{1,1} ilist_{1,4},…])$->$(t_1,ilist_final)$

$ilist_{i,j}$: the j’th inverted list fragment for term i

注意每个 reducer 里的 inverted list 都是完整的，每个 reducer 相当于存了个 result block，每个 block 包括不同的 term，每个 term 只在一个 block 里出现。

如果要创建 partitioned inverted list，只用在 key 里加上一个 partition id 即可。

Map:
$(docid_1,content_1)$ -> $([p,t_1],ilist_{1,1})([p,t_2],ilist_{2,1})([p,t_3],ilist_{3,1})$
Combine:
Sort by t & combine $([p,t_1] [ilist_{1,2} ilist_{1,3} ilist_{1,1},…])$->$([p,t_1],ilist_{1,27})$
每个 output inverted list 包含了一系列文档
Shuffle by p
Sort by [p,t]
$([p,t_4] ilist_{4,1}) ([p,t_1] ilist_{1,3})$->$([p,t_1],ilist_{1,2})([p,t_1],ilist_{1,4})([p,t_4],ilist_{4,1})$
Reduce
$([p,t_1] [ilist_{1,2} ilist_{1,1} ilist_{1,4},…])$->$([p,t_1],ilist_final)$

Inverted list compression

概念上来讲 inverted list 看起来像一个 object

# apple
df: 4356
docid: 42
tf: 3
locs: 14
      83
      157
      94
docid: 94
...

而实际上它在磁盘中只是一串数字

通常 intered list 会被压缩，目的不同，选择的压缩方法也就不同。要节省空间我们就用 aggressive compression algorithms，要节省时间我们就用 simple compression algorithms。现在我们最主要的目的是节省 query 时间，用的压缩算法主要有

Gap encoding
Restricted variable-length(RVL) encoding

Delta Gap

Delta Gap 的基本思想是保存数字的差值而不是数字本身，意义在于

增加较小的数字的概率
更 skewed 的分布
降低信息熵

Variable Byte Encoding

Variable Byte Encoding 存了一串 bytes，每个 byte 由开头 1 位 flag 和 7 位的 payload（the number）组成。flag 为 0，表示不是最后一个 byte，flag 为 1 表示这是最后一个 byte。通过连接 payload 来重建 number。

好处是编码和解码的效率都很高，可以找到第 n 位数字而不用 decode 之前的数字。

Example

[0..2^7-1]:      1 byte : 1xxxxxxx
[2^7...2^14-1]:  2 bytes: 0xxxxxxx1xxxxxxx
[2^14...2^21-1]: 3 bytes: 0xxxxxxx0xxxxxxx1xxxxxxx
...
Decimal: 5
Binary: 00000000 00000000 00000000 00000101
# 照抄最后7位，第一位补上1
Compressed: 10000101
Decimal: 127
Binary: 00000000 00000000 00000000 01111111
# 照抄最后7位，第一位补上1
Compressed: 11111111
Decimal: 128
Binary: 00000000 00000000 00000000 10000000
# 照抄最后7位，第一位补上0，再往前找7位，照抄，第一位补上1
Compressed: 00000000 10000001
Decimal: 131
Binary: 00000000 00000000 00000000 10000011
# 照抄最后7位，第一位补上0，再往前找7位，照抄，第一位补上1
Compressed: 00000011 10000001

Summary

最高效的压缩算法比 variable byte encoding 节省 15%－20% 的空间，但是比 restricted variable length encoding 要慢。注意我们这里要把握的原则是 “Disks are cheap, and speed is important”，所以 Restricted variable length compression 还是非常通用的。

压缩不包含地址信息的 inverted file，所用空间是 original text 的 10%，压缩包含地址信息的 inverted file，所用空间是 original text 的 15%-20%。

Inverted list Optimization

Skip lists

我们可以跳过一些文档来减少 I/O，减少计算。

Operators

#NEAR,#WINDOW,#SYN,Boolean AND，skip lists 在这些 operator 中会非常有效。回顾 #NEAR 的算法，假设 query 是 #NEAR/3(a b)，包含 a 的第一个 docid 是 59356，包含 b 的第一个 docid 是 43，之前的做法是让 b 的 doc pointer 不断指向 next，直到 a,b 的pointer 指向同一篇文档，如果考虑 skip lists，就可以直接指向 a 的 docid，（调用 docIteratorAdvanceTo(doc_id_a)方法）。

Score calculation (Top-Docs)

有些 inverted list 太长了，而大多 query 只需要返回 <100 的文档，所以我们可以截取 inverted list 里 top docs 的部分，这样就能提高效率，代价是更低的召回率。

怎么找到 Top-Docs

tf
PageRank

怎么对 Top-Docs 排序

Order by doc id
Order by tf

How many terms are frequent enough to have a top-docs list?
根据 Zipf’s Law
$$Rank * Frequency = A * N$$

所以 ctf>=800 的 term 大概占比 ${A*N/800 \over A * N}=1/800=0.125%$

why 800?
假设一个 inverted list 有5个 integer，没压缩就有 16 bytes，30%压缩比，压缩了有 5 bytes，linux filesystem page size是 4096 bytes, 所以有4096/5=819条 inverted list 能 fit in one page

假设 vocabulary 有 1,000,000 个 term，那么大概只有 1,250 个 top-docs lists，每个 list 大概 4-8KB，一共占 5-10 MB。

Multiple inverted lists per term

有些 operator 并不需要 tf，像 unranked boolean operators，有些 operator 并不需要 locations，像 #SUM,#WEIGHT,#AND,#OR,#ANDNOT,…，而 inverted lists with locations 会产生 I/O 浪费，对没有 location 的 inverted list，我们只用存 docid, tf 两个 integer，而对存了 location 的 inverted list,假定我们对每篇文档多用了 1.5 个 integer，那么我们其实浪费了 42% 的 I/O。所以对于每个 term，我们可以存两份 inverted list，一份有 location，一份没有，对不需要 location 的 operator，我们就直接访问没有location 的 inverted list，这样就能避免不必要的 I/O，当然代价是额外的磁盘空间。

我们要对每个 term 都存两个 inverted list 吗？ 其实并不需要。因为大概只有 0.125% 对 term 有 topdocs/champion list，其它 term 对 inverted list 都很短。所以我们只用对 frequent terms 建两个 inverted list 就可以啦。

Index updates

corpus 并不是静态的，随着文档的增加，我们需要将新的 term 加入词典，对已有的 inverted list 进行更新，然而这个代价非常的大。最简单的索引更新方法是 周期性地对 corpus 进行索引重构，如果 corpus 更新次数不多，而且能接受新文档检索的一定延迟，也有足够资源支持建立新索引时让旧索引继续工作，那么周期性索引重构不失为一种好选择。另外一种解决方法是保持两个索引：一个主索引，一个辅助索引，辅助索引用于存储新文档信息，保存在内存中，检索时可以同时遍历两个索引并将结果合并。如果有文档删除，可以把删除的 docid 记录在一个 delete list 里，在返回结果之前利用它过滤掉已经删除的文档。文档的更新通过先删除后重新插入实现。当辅助索引变得很大时，就将它合并到主索引中。

Storing document structure

Treat each element as independent of other elements

简单明了的结构，简单、高效，对 shallow structure 的 document 非常有效。在这种结构下，我们分别保存每个 field 下的词汇，可以有一下两种形式

FIELD::TERM
(FIELD,TERM)

Treat elements as part of an element hierarchy

$Document \supset Section \supset Subsection$ 非常灵活的结构，更好的符合用户需求，基本思想是 “Terms in “Subsection” should also appear in “Section”” 对 complex structure 非常有效。